package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/winner-of-the-linked-list-game'>链表游戏的获胜者(Winner of the Linked List Game)</a>
 * <p>给定长度为偶数 ，包含整数的链表的 head 节点。</p>
 * <p>每个 奇数编号 的节点包含一个奇数，并且每个 偶数编号 的节点包含一个偶数。</p>
 * <p>我们把每个偶数编号的节点和它的下一个节点叫做一个 对，例如编号为 0 和 1 的节点是一对，编号为 2 和 3 的节点是一对，以此类推。</p>
 * <p>
 * 对于每个 对，我们比较对中节点的值：
 *     <ul>
 *         <li>如果奇数节点更大，"Odd" 队得一分。</li>
 *         <li>如果偶数节点更大，"Even" 队得一分。</li>
 *     </ul>
 * </p>
 * <p>返回分数更 高 的队名，如果分数相同，返回 "Tie"。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：head = [2,1]
 *      输出："Even"
 *      解释：链表中只有一个对 (2,1)。因为 2 > 1，偶数队得分。
 *      因此，答案是 "Even"。
 *
 *  示例 2：
 *      输入：head = [2,5,4,7,20,5]
 *      输出："Odd"
 *      解释：此链表中有 3 对。让我们分别对每一对进行分析：
 *          (2,5) -> 因为 2 < 5，奇数队得分。
 *          (4,7) -> 因为 4 < 7，奇数队得分。
 *          (20,5) -> 因为 20 > 5，偶数队得分。
 *          奇数队得 2 分，偶数队得 1 分，奇数队得分更高。
 *          因此，答案是 "Odd"。
 *
 *  示例 3：
 *      输入：head = [4,5,2,1]
 *      输出："Tie"
 *      解释：此链表中有 2 对。让我们分别对每一对进行分析：
 *          (4,5) -> 因为 4 < 5，奇数队得分。
 *          (2,1) -> 因为 2 > 1，偶数队得分。
 *          每队得 1 分。
 *          因此，答案是 "Tie"。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点的数字在范围 [2, 100] 内。</li>
 *     <li>链表中的节点数为偶数。</li>
 *     <li>1 <= Node.val <= 100</li>
 *     <li>每个奇数编号节点的值都是奇数。</li>
 *     <li>每个偶数编号节点的值都是偶数。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/8 14:24
 */
public class LC3062WinnerOfTheLinkedListGame_S {
    static class Solution {
        public String gameResult(ListNode head) {
            int odd = 0;
            int even = 0;
            while (head != null && head.next != null) {
                int evenVal = head.val;
                int oddVal = head.next.val;
                if (evenVal > oddVal) {
                    even++;
                } else {
                    odd++;
                }
                head = head.next.next;
            }
            return even > odd ? "Even" : even == odd ? "Tie" : "Odd";
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(2);
        head1.next = new ListNode(1);

        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(5);
        head2.next.next = new ListNode(4);
        head2.next.next.next = new ListNode(7);
        head2.next.next.next.next = new ListNode(20);
        head2.next.next.next.next.next = new ListNode(5);

        ListNode head3 = new ListNode(4);
        head3.next = new ListNode(5);
        head3.next.next = new ListNode(2);
        head3.next.next.next = new ListNode(1);

        Solution solution = new Solution();
        System.out.println(solution.gameResult(head1));
        System.out.println(solution.gameResult(head2));
        System.out.println(solution.gameResult(head3));
    }
}
